package com.jinan.algorithm.Backtrace;


public class IslandCounter {
    public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };

        System.out.println(countIslands(grid)); // 输出应为 3
    }

    public static int countIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }

    /**
     * 岛屿类问题的通用解法、DFS 遍历框架
     * @param grid
     * @param row
     * @param col
     */
    private static void dfs(char[][] grid, int row, int col) {
//        判断 base case
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != '1') {
            return;
        }
        // 如果这个格子不是岛屿，直接返回
//        if (grid[row][col] != '1') {
//            return;
//        }

        grid[row][col] = '2'; // 标记为已访问

        // 访问上、下、左、右四个相邻结点
        dfs(grid, row - 1, col); // 上
        dfs(grid, row + 1, col); // 下
        dfs(grid, row, col - 1); // 左
        dfs(grid, row, col + 1); // 右
    }

    // 判断坐标 (r, c) 是否在网格中
    boolean inArea(int[][] grid, int r, int c) {
        return 0 <= r && r < grid.length
                && 0 <= c && c < grid[0].length;
    }

}
